题目分析

好像在哪里见到过类似的题目，划分为k个相等的子集(Leetcode 698)。但是难度比那个题目要高一些。

数学+深度优先搜索

本题难点在于直接暴搜是完全不行的，因为数据范围是30，虽然最多搜索15个元素。

这里用到了对称的思想，如果搜索超过15个元素，比如16个，等价于另一个数组搜索14个。

但是这15个元素到底应该选择多少个是不确定的，因此暴搜的时间复杂度是O(n!)，15! = 1e12，所以会TLE。

因此要使用数学的思想优化，题目是将数组拆分成两个部分，每个部分平均值相等。我们不妨记平均值为A，两个部分分别记作m1和m2，平均值相等表示m1和m2两个部分中每个元素分别减去A，剩余元素之和为0。

此时有一个巧妙的算法，我们将原数组按长度一般分成p1和p2，p1数组如果某些元素之和为s，那么如果p2数组中某些元素之和恰巧为-s，那么将这两部分元素组合起来，那么元素之和就是0。

所以题目转变为从p1数组中给结果数组m1选出一部分值，和为s，然后从p2数组中给结果数组m2选出一部分和为-s的元素。

算法的时间复杂度为O(n2^n)，空间复杂度为O(2^n)。其中n为数组长度的一半，最大为15，满足条件。

这里有三个小技巧

如果某些元素和为0，说明将这些元素划分在一组即可满足条件，直接return true即可。
计算p1数组时，从1开始考虑，因为如果全都不选，那么可以认为从p2数组中选一部分，在后面计算p2数组时，如果和为0也会return true。因此不需要对p1数组全不选的情况特判。
计算p2数组时，不能全选，因为全选，因为如果p2全选和为s，那么在p1数组中也全选，和一定等于-s，此时结果m2数组为空，不符合条件。

对于第三点，有的小伙伴有疑问，那么p2数组如果全选，p1数组部分元素之和等于-s呢？是不是会漏掉return true的情况？这样的话，p1数组其他部分的元素之和会等于0，在遍历p1的时候就return true了，因此也不需要对p2全选进行特判。

有的小伙伴还能想到一种场景，如果p2全选都为0，是不是也会漏掉return true的情况？其实和上面一样的，如果p2全选都是0，那么p1全选也一定是0，在遍历p1的时候也会return true，这也是p1需要遍历全部元素，p2不需要遍历全部元素的原因。

class Solution {
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length;
        int sums = Arrays.stream(nums).sum();
        for (int i = 0; i < n; i++) {
            nums[i] = nums[i] * n - sums;
        }
        int p1 = n / 2;
        HashSet<Integer> set1 = new HashSet<>();
        for (int i = 1; i < (1 << p1); i++) {
            int sum = 0;
            for (int j = 0; j < p1; j++) {
                if ((i & (1 << j)) != 0) {
                    sum += nums[j];
                }
            }
            if (sum == 0) {
                return true;
            }
            set1.add(sum);
        }
        
        int p2 = n - p1;
        for (int i = 1; i < (1 << p2) - 1; i++) {
            int sum = 0;
            for (int j = 0; j < p2; j++) {
                if ((i & (1 << j)) != 0) {
                    sum += nums[p1 + j];
                }
            }
            if (sum == 0 || set1.contains(-sum)) {
                return true;
            }
        }
        return false;
    }
}

动态规划

本题还可以使用动态规划的方法求解，不过本题难点在于不是普通的二维dp，而是二维可变dp。

设dp[i]是一个集合，表示有i个元素，元素之和的种类数。当遍历到第k个元素时，dp[i]集合需要从dp[i - 1]集合中遍历每一种情况。

这里也有一个数学技巧，当最终某个数组元素个数是m，之和为p，全部元素数量为n，之和为s，那么return true等价于p / m = s / n。因此如果s x m % n全都不等于0，那么可以直接return false。

算法的时间复杂度为O(n^2 \times sum(nums))，空间复杂度为O(n \times sum(nums))。其中n为数组的长度，sum(nums)为数组元素之和。

class Solution {
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int m = n / 2;
        boolean flag = false;
        for (int i = 1; i <= m; i++) {
            if ((sum * i) % n == 0) {
                flag = true;
                break;
            }
        }
        if (!flag) {
            return false;
        }
        HashSet<Integer>[] dp = new HashSet[m + 1];
        for (int i = 0; i <= m; i++) {
            dp[i] = new HashSet<>();
        }
        dp[0].add(0);
        for (int x : nums) {
            for (int i = m; i > 0; i--) {
                for (int val : dp[i - 1]) {
                    int cur = val + x;
                    if (cur * n == sum * i) {
                        return true;
                    }
                    dp[i].add(cur);
                }
            }
        }
        return false;
    }
}

刷题总结

本题的难度不小，刚刚开始做的时候都TLE了，小伙伴们可以多挑战一些难题，对算法的提升很有帮助。